package oj;

import java.util.*;

/**
 * @author 郝文雪
 * @date 2022/7/24 17:23
 * @Description Test
 */
public class LC373 {
    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> q=new PriorityQueue<>(k,new Comparator<List<Integer>>(){
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        for(int i=0;i<Math.min(k,nums1.length);i++){
            for(int j=0;j<Math.min(k,nums2.length);j++){
                if(q.size()<k){
                    List<Integer> res=new ArrayList<>();
                    res.add(nums1[i]);
                    res.add(nums2[j]);
                    q.add(res);
                }else{
                    int top=q.peek().get(0)+q.peek().get(1);
                    if(top > nums1[i]+nums2[j]){
                        q.poll();
                        List<Integer> res=new ArrayList<>();
                        res.add(nums1[i]);
                        res.add(nums2[j]);
                        q.add(res);
                    }else{
                        break;
                    }
                }

            }
        }
        List<List<Integer>> list=new LinkedList<>();
        for(int i=0;i<k && !q.isEmpty();i++){
            list.add(q.poll());
        }
        return list;
    }
}
